//---------------------------------------------------
// Purpose: Functions to generate and search arrays
// Author:  John Gauch
//---------------------------------------------------
#include <iostream>
using namespace std;

// Function that creates random data
void random_data(int array[], int size)
{
   for (int i=0; i<size; i++)
      array[i] = random() % 100;
}

// Function that creates sorted data
void sorted_data(int array[], int size)
{
   array[0] = random() % 10;
   for (int i=1; i<size; i++)
      array[i] = array[i-1] + random() % 10;
}

// Function that prints data
void print_data(int array[], int size)
{
   for (int i=0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}

// Function that searches array and returns result
bool search(int number, int array[], int size)
{
   // search for number in data array
   bool found = false;
   for (int i=0; i<size; i++)
   {
     cout << "checking " << i << " " << array[i] << endl;
     if (array[i] == number)
        found = true;
   }
   return found;
}

// Function that searches array and uses reference parameter
void search(int number, int array[], int size, bool &found)
{
   // search for number in data array
   found = false;
   for (int i=0; i<size; i++)
   {
     cout << "checking " << i << " " << array[i] << endl;
     if (array[i] == number)
        found = true;
   }
}

// Function that checks if array is sorted and returns result
bool is_sorted(int array[], int size)
{
   // check if array is in sorted order 
   bool sorted = true;
   for (int i=1; i<size; i++)
   {
     if (array[i-1] > array[i])
        sorted = false;
   }
   return sorted;
}

// Function that checks if array is sorted and uses reference parameter
void is_sorted(int array[], int size, bool &sorted)
{
   // check if array is in sorted order 
   sorted = true;
   for (int i=1; i<size; i++)
   {
     if (array[i-1] > array[i])
        sorted = false;
   }
}

// Function that searches array and returns data location 
int binary_search(int value, int array[], int min_index, int max_index)
{
   // Search array using divide and conquer approach
   int mid_index = (min_index + max_index) / 2;
   while ((array[mid_index] != value) && (max_index >= min_index))
   {
      // Change min to search right half
      if (array[mid_index] < value)
         min_index = mid_index+1;
   
      // Change max to search left half
      else if (array[mid_index] > value)
         max_index = mid_index-1;

      // Update mid location
      mid_index = (min_index + max_index) / 2;
   }
   
   // Return results of search
   if (array[mid_index] == value)
      return(mid_index);
   else
      return(-1);
}

int main()
{
   // Declare and initialize array
   const int SIZE = 20;
   int data[SIZE] = {0};
   srandom(time(NULL));
   sorted_data(data, SIZE);
   print_data(data, SIZE);

   // Test the is_sorted function
   bool sorted = is_sorted(data, SIZE);
   if (sorted)
      cout << "the array was sorted\n";
   else
      cout << "the array was NOT sorted\n";

   // Get user input
   int number = 0;
   cout << "enter a number: ";
   cin >> number;

   // Test the binary search function
   int index = binary_search(number, data, 0, SIZE-1);
   if (index >= 0)
      cout << "found " << number << " at location " << index << endl;
   else
      cout << "didn't find " << number << " in the array" << endl;
}